##############################################################
# 题目7,：查找最大子积 [-1,4,-1]  -->4  [-1,2,4,-1] -->8  [-1,2,3,4,-1] -->24
lst=[5,-6,8,7-4,9,1-9,2];
result=[];
from functools import reduce
def get_max_multi(lst):
    for i in range(len(lst)):
        for j in sorted(range(len(lst)),reverse=True):
            if i<j:
                res=reduce(lambda x,y:x * y,lst[i:j+1])
                result.append(res)
    return max(result)
print(get_max_multi(lst))

'''
-1  2  -7  
'''

# 第一行为整个列表中的数据依次相乘，第二行开始动态规划
def get_max_multi2(lst):
    result=[];
    A0 = lst;  # 用来存放第一行的数据
    Max=0
    for i in range(len(lst)):
        B=[];
        for j in range(len(lst)):
            B.append(0)
        for j in range(i,len(A0)):
            #得到第一行的数据，初始值
            if i==j:
                B[j]=A0[i];
            elif i==0 and j>=2:
                b=reduce(lambda x,y:x * y,A0[1:j])
                B[j]=b
            # 开始动态规划，a[i][j]=max(a[i-1][j])*a[i][j-1]
            else:
                if lst[j]>0:
                    c=max(A0[i:j])
                else:
                    c=min(A0[i:j])
                b=c*lst[j]
                B[j] = b
        result.append(B)
        A0=B
    # 得到每一次的最大值
    if max(B)>Max:
        Max=max(B)
    return Max

print("动态规划得到的最大值为：",get_max_multi2(lst))